\documentclass[11pt, letterpaper, twoside, english]{book}

%\topmargin  0.25in
%\headheight 0.2in
%\headsep    0.3in
%\textheight 8.5in
%\textwidth  6.0in
%\footskip   0.7in

\setlength{\parskip}{1.5ex}


\usepackage[activeacute]{babel}
\usepackage[dvips]{graphicx}
\usepackage{amsfonts, amssymb}
\pagestyle{plain}

\begin{document}
\frontmatter
\thispagestyle{empty}

\vspace*{2.5cm}
\noindent\makebox{\begin{minipage}{\textwidth}{
\flushright \Huge Introduction to the \\
Sartoris Microkernel Architecture

}

\noindent\rule{\textwidth}{4pt}

\noindent\flushright { \large Design concepts and implementation notes for the x86 platform. }

\end{minipage}
}

\vspace{10cm}
\noindent\makebox{\begin{minipage}{\textwidth}{
\flushright by Santiago Bazerque and Nicol\'as de Galarreta \\[1.5ex]
for Sartoris version 1.5, \today.

}
\end{minipage}
}

\newpage
\thispagestyle{empty}
\cleardoublepage

\chapter{Abstract}

The Sartoris project aim is to develop a portable policy-free microkernel that provides a simple processor abstraction, yet a powerful enough one to support a full featured operating system. Therefore, boot primitives and system calls to perform crude process creation, (shared) memory management and asynchronous message-passing are the only features directly supported by the kernel. The rest of the functionality of the operating system, including the process-manager, memory-manager, filesystems, device drivers, \ldots{} are to be implemented outside of the kernel.


\tableofcontents

\mainmatter

\chapter{Microkernel design}

\section{General considerations}
Any operating system designed to run modern hardware must overcome the (rather complicated) details of the management of the central processors and their memory management units. In most processor architectures, this implies using specific machine instructions and maintaining a set of data structures in memory from which the hardware can obtain the current state of the system. Furthermore, the handling of interrupt requests and the construction and maintenance of the page tables are themselves nontrivial tasks, increasing the overall complexity of the system.

Therefore, it seems reasonable to encapsulate the routines that interact directly with the processor, and that is what the Sartoris microkernel intends to do. Moreover, in order to provide a suitable abstraction to the operating system, the microkernel does not need to provide many other functions. The system calls provided by Sartoris can be grouped as follows:\footnote{Every processor architecture has unique features that must be handled in the kernel (i.e. performance monitoring hardware). A small number of architecture specific system calls will provide the necessary cpu dependent functions. }

\begin{enumerate}
\item[]\textbf{Task and thread management.} These system calls cover the creation of processor tasks and threads. Sartoris does not, however, load processes from disk or perform any scheduling of the CPU. These chores are to be performed by services running on top of the microkernel (usually, a process-manager task). Under Sartoris, an interrupt handler is just a special thread that is invoked by the microkernel every time the corresponding interrupt request line is raised. Hence, the a scheduling thread may be created by binding an ordinary thread to the timer interrupt.
\item[]\textbf{Memory management.} This subsystem presents an abstracted view of the paging mechanism of the underlying processor, as well as an implementation of inter-task memory sharing through Sartoris SMOs (shared memory objects), which are chunks of binary data that can be easily accessed from multiple tasks. Again, the microkernel does not perform any paging directly (except in exceptional cases like interprocess communication, whence some temporary mappings may be created and later destroyed during the execution of a system call). It just provides support for the easy creation and modification of page tables, (mostly) independently of the processor page table format and peculiarities.
\item[]\textbf{Message passing.} The kernel provides an asynchronous messaging system, in the form of a set of ports assigned to each task. Each port functions as a mailbox where fixed-sized messages from other tasks are received. These system calls cover the creation, deletion and management of ports.
\end{enumerate}

\noindent{}Before each of the subsystems is further described, the main issues considered in the design will be reviewed:
\begin{enumerate}
\item[] The microkernel should present a simple yet effective abstraction of the processor to the operating system. The services offered by the microkernel should be clearly defined and easy to understand.
\item[] In order to obtain effective portability, a suitable interface that encapsulates the architecture-dependent sections of the kernel code has to be defined.
\item[] Kernel services should be provided in a policy-independent way, whenever this is possible. The design of the operating system should not be over-restricted by the underlying microkernel architecture.
\item[] The design of the microkernel should allow an efficient implementation of the most common operating system functions, considering the inherent constraints that the microkernel architecture imposes to the system.
\item[] A secure execution envirnoment must be provided for the operating system.
\end{enumerate}

\section{Introduction and sources organization}
A kernel may be defined as the set of functions that it implements. The full Sartoris system call set is declared in the file \textsf{include/sartoris/syscall.h}:

\begin{sf}
\noindent /* sartoris system calls */ \\
\\
\#ifndef SYSCALL \\ 
\#define SYSCALL \\
\\
\#include $<$sartoris/kernel.h$>$ \\
\\
/* multitasking */ \\
int create\_task(int address, struct task *tsk, int *src, int init\_size); \\
int destroy\_task(int task\_num); \\
int get\_current\_task(void); \\
\\
/* threading */ \\
int create\_thread(int id, struct thread *thr); \\
int destroy\_thread(int id); \\
int run\_thread(int id); \\
int set\_thread\_run\_perm(int thread, int perm); \\
int set\_thread\_run\_mode(int priv, int mode); \\
int get\_current\_thread(void); \\
\\
/* paging */ \\
int page\_in(int task, void *linear, void *physical, int level, int attrib); \\
int page\_out(int task, void *linear, int level); \\
int flush\_tlb(void); \\
int get\_page\_fault(struct page\_fault *pf); \\
\\
/* interrupt handling */ \\
int create\_int\_handler(int number, int thread, int nesting, int priority); \\
int destroy\_int\_handler(int number, int thread); \\
int ret\_from\_int(void); \\
int get\_last\_int(void); \\
\\
/* message-passing */ \\
int open\_port(int port, int mode);\\
int close\_port(int port);\\
int set\_port\_perm(int port, int task, int perm);\\
int set\_port\_mode(int port, int priv, int mode);\\
int send\_msg(int to\_address, int port, void *msg); \\
int get\_msg(int port, void *msg, int *id); \\
int get\_msg\_count(int port); \\
\\
/* memory sharing */ \\
int share\_mem(int target\_task, void *addr, int size, int perms); \\
int claim\_mem(int smo\_id); \\
int read\_mem(int smo\_id, int off, int size, void *dest); \\
int write\_mem(int smo\_id, int off, int size, void *src); \\ 
int pass\_mem(int smo\_id, int target\_task); \\
int mem\_size(int smo\_id); \\
\\
\\
\#ifdef \_METRICS\_\\
int get\_metrics(struct sartoris\_metrics *m);\\
\#endif\\
\\
\#ifdef \_SOFTINT\_\\
int run\_thread\_int(int id, void *eip, void *stack);\\
\#endif\\
\\
\#endif \\ \\
\end{sf}
The architecture-independent part of the system calls implementation is contained in the files in the subdirectory \textsf{mk}. These files implement the algorithms and data structures that are independent of the platform the microkernel is being compiled for. The object files obtained from these sources have to be linked with the implementation of the low level functions for the target processor, which should be \textsf{arch/target/kernel/cpu-arch.o}, where \textsf{target} is a symlink to the desired architecture directory. The set of GNU makefiles provided with the sources takes care of the complete compile and link cycle.  The low-level interface is described in section \ref{sec:lowlevelinterface}. 

\section{Tasks and threads}
All the processing (even interrupt handling) in a Sartoris based system is done in the context of a task, and a thread within that task. \\
A task is composed by a virtual address space (defined by a set of page tables) and communication mechanisms (ports and shared memory objects). It is identified uniquely by a number between zero and \textsf{MAX\_TSK}\footnote{A constant defined by the implementation}, which is the parameter \textsf{address} passed to the system call \textsf{create\_task(int address, struct task *tsk, int *src, int init\_size)}, where \textsf{*src} points to the beginning of the task image within the calling task's address space, and \verb|*tsk| points to a structure of the type \\
\\
\begin{sf} \noindent struct task \{ \\
\indent  int mem\_adr; \\
\indent  int size; \\
\indent  int priv\_level; \\
\}; \\
\end{sf}
\\
\noindent where \textsf{mem\_adr} indicates the physical address where this task should be placed in main memory\footnote{The organization of the tasks in physical memory is therefore under absolute control of the operating system.}, \textsf{size} indicates the size (in words) of the task being created, and \textsf{priv\_level} indicates its privilege level. This number might be used by the operating system to restrict the ability to send messages to ports and to run specific threads using privilege levels. Zero is the most privileged level, and levels zero and one have a special meaning to the microkernel, because they are the only levels that can access the input$/$output space. Also, the system calls to create and destroy tasks, threads and interrupt handlers are restricted to tasks running in privilege level zero. The system call \textsf{ret\_from\_int} is restricted to levels zero and one.\footnote{Notice that the numerical privilege levels used by the microkerenl are independant of those defined by the underlying processor architecture. For example, threads running with mircrokerenel privlege 0 in the x86 implementation of Sartoris are running with a processor privilege level of 1, since level 0 is being used by the microkernel itself.}
Tasks are destroyed using the similar function \textsf{destroy\_task}, which receives the address of the task being destroyed.

A thread is a processor state associated with a given task. The maximum amount of concurrent threads is determined by the constant \textsf{MAX\_THR}. A task might have zero, one, or more threads. Threads are created using the system call \textsf{create\_thread(int id, struct thread *thr)}. The parameter \textsf{id} is an integer that uniquely identifies each thread, and must not exceed \textsf{MAX\_THR}-1. The structure \textsf{thread} is defined as \\
\\
\begin{sf} \noindent struct thread \{ \\
\indent  int task\_num; \\
\indent  int invoke\_mode; \\
\indent  int invoke\_level; \\
\indent  int ep; \\
\indent  int stack; \\
\}; \\
\end{sf}
\\
where \textsf{task\_num} is the task that defines the context in which this thread is to be created (which must have been already created), \textsf{ep} is this thread's entry point, \textsf{stack} is the initial stack value, and invoke mode is one of the following:
\begin{enumerate}
\item[] \textsf{PERM\_REQ}: In this mode, it is necessary (additionally to the privilege level constraints) to have specific authorization (obtained through the function \textsf{set\_thread\_run\_perm}) to run this thread.\footnote{Right now, on implementation for Sartoris 1.5, this functionallity is no longer supported. Perhaps on a future version it will be supported again.}
\item[] \textsf{PRIV\_LEVEL\_ONLY}: In this mode only the usual privilege level constraints are applied to the function \textsf{run\_thread} applied to this thread\footnote{see the description of the function \textsf{run\_thread} below}.
\item[] \textsf{DISABLED}: The thread is disabled, and it can't be invoked by anyone.
\end{enumerate}
The value of the field \textsf{invoke\_level} indicates the numerically higher privilege level that can invoke this thread. 


Threads are destroyed using the \textsf{destroy\_thread} system call\footnote{It may be worth noting that the currently running thread can't destroy itself.}, and may be started (or resumed) by interrupt requests signaled to the processor, software generated interrupts, exceptions, traps and the already mentioned \textsf{run\_thread} system call.

As a non-restrictive policy, the \textsf{run\_thread} system call can be used by threads running at every privilege level, but there are restrictions regarding which threads might be invoked. The target task protection mode must not be \textsf{DISABLED}, the privilege level of the invoking task must be numerically lower or equal than the \textsf{invoke\_level} of the target task, and if the protection mode of the target task is equal to \textsf{PERM\_REQ}, the invoking task must have been authorized by the target task through the function \textsf{set\_thread\_run\_perm}.
A thread can modify it's \textsf{invoke\_mode} using the \textsf{set\_thread\_run\_mode} system call at any time. 
       
\section{Messaging system}
The kernel provides an asynchronous inter-task message system through the \textsf{send\_msg}, \textsf{get\_msg} and \textsf{get\_msg\_count} system calls. The messages have a fixed size defined by the implementation, and the kernel guarantees that messages arrive in FIFO order, but each message queue has a maximum capacity which is also implementation-defined. When a message is sent using the function \textsf{int send\_msg(int to\_address, int port, void *msg)}, the contents of the message pointed by \textsf{msg} are copied to the queue for port number \textsf{port} of task \textsf{to\_address}. The receiving of messages is done in an analogous fashion using the function \textsf{int get\_msg(int port, void *msg, int *id)}, which removes the fist message in the supplied \textsf{port}'s queue and copies it's contents to the address \textsf{msg}. The variable \textsf{id} is used to return the id of the sender task. Both functions return 0 on success. 
The function \textsf{int get\_msg\_count(int port)} returns the amount of messages waiting in the queue of the supplied port.
Before a port can be usde to receive messages, it must be opened using the \textsf{open\_port} system call, setting it's protection mode (see below) and the numerically higher privilege level that can send messages to this port. When a port is closed using the \textsf{close\_port} system call, the associated message queue is flushed and the port becomes available to be used again. The amount of simultaneous ports a task can open at any given time is defined by the constant \textsf{MAX\_TSK\_OPEN\_PORTS} located in the header file \textsf{/include/sartoris/message.h}. 

In order to provide a secure messaging system, Sartoris defines the following port protection modes:
\begin{enumerate}
\item[]\textsf{PERM\_REQ}: When a port's protection mode is set to \textsf{PERM\_REQ}, a task can send messages to this port if it has been authorized through the \textsf{set\_port\_perm} system call, and it's privilege level is numerically lower or equal than the port's privilege level.
\item[]\textsf{PRIV\_LEVEL\_ONLY}: The privilege level of the task sending the message must be numerically lower or equal than the port's privilege level.
\item[]\textsf{DISABLED}: If a task wishes to deny access to a port, this is the protection mode it ought to have.
The protection mode for a port can be modified using the \textsf{set\_port\_mode} system call. Permissions can be granted (or removed) to individual tasks using the \textsf{set\_port\_perm} system call.
\end{enumerate} 

Creation and deletion of ports is done with the \textsf{create\_port}, \textsf{delete\_port} and \textsf{delete\_task\_ports} functions. It's important to note that the whole \textsf{msg\_container} has to be initialized with the \textsf{init\_msg} function before using any other function. Messages on ports are managed with the \textsf{empty}, \textsf{enqueue} and \textsf{dequeue} functions. All these functions are implemented in \textsf{mk/message.c}.

\section{Memory management} \label{sec:memorymanagement}

The address space of each task is, as was mentioned earlier, defined by a set of page tables. Even though the details of the paging subsystem vary from processor to processor (i.e. levels of indirection, exact format of a page table entry, etc.), the microkernel strives to present a simple abstraction of the paging mechanism. Again, paging operations should be directed by a process (or several processes) running on top of the microkernel, and using appropriate system calls to build and destroy the page mappings. The same function, \textsf{int page\_in(int task, void *linear, void *physical, int level, int attrib)}, is used to insert page tables and individual page entries into the page table structure of a task. The parameter \textsf{level} is used to distinguish between the former and the latter. For example, the x86 implementation of Sartoris treats level 0 as page directory, level 1 as page table and level 2 as individual page entry. Of course, this depends upon the levels of indirection implemented by the processor. The parameter \textsf{task} indicates the id of the task whose page tables are to be modified, the \textsf{linear} and \textsf{physical} pointers indicate the mapping whose creation is being requested. Finally, the parameter \textsf{attrib} supports the following attributes:

\begin{enumerate}
\item[] \textsf{PGATT\_CACHE\_DIS}: the page should be marked as cache-disabled.
\item[] \textsf{PGATT\_WRITE\_ENA}: the page should be marked as read-write.
\item[] \textsf{PGATT\_WRITE\_THR}: the page should be marked as write-through (i.e. don't cache writes).
\end{enumerate}

Which attributes are supported at each level depends upon the platform. Bear in mind that the page levels have to be inserted in the correct order, since the microkernel uses no intermediate structures in the construction of the page tables. For example, if the paging system has a page-directory, page-tables structure (as in the x86 processors), the directory must be inserted first, then the relevant page tables and finally the individual page entries. Destruction of mappings functions symetrically through the system call \textsf{int page\_out(int task, void *linear, int level)}. Removing a page table will disable all its page table entries as well, and removing the page directory will disable the entire address space of the task.

The functions \textsf{int flush\_tlb(void)} and \textsf{int get\_page\_fault(struct page\_fault *pf)} flush any translation lookaside buffers the processor may have, and retrieve information about the last page fault.

\textbf{kernel internals:} In current implementations, the microkernel has its own set of page tables to access the low memory area where its own code and data structures reside, that is injected into every task's page directory upon insertion. The page mangling functions described above take the appropiate measures to prevent user programs from disrupting the microkernel address space. To access user memory, the kernel uses the same page tables as the user processes do. Hence, the presence in memory of user data needed by system calls cannot be guaranteed by the microkernel. This is specially delicate when the microkernel must access a lock in order to perform the system call. Usually, critical sections are implemented in single processor kernels by disabling the interrupts. However, a page fault may well occur with interruptions disabled, thus disrupting the locking mechanism. The solution to this problem is twofold: for small structures received from user space, the structure is copied to the kernel stack before any locking is performed, and therefore page faults, if present, can be resolved without harm. For larger memory access (for example, in the implementations of the functions \textsf{read\_mem} and \textsf{write\_mem}), each time the microkernel must access a new page from user space, the presence of the relevant page in memory is checked and, if missing, a page fault is issued by the microkernel (not by the processor) after releasing any pertinent locks and saving the necessary information to allow the system call to continue normally and securely after the page fault has been resolved.


The microkernel must supply a mechanism to perform memory sharing. Therefore, each task can access a set of Shared Memory Objects which allow other tasks to access its address space in a controlled way. However, there is no memory aliasing, and access is limited to reading from and writing to the shared sections using system calls that copy memory contents from one task address space to another.

The system call \textsf{int share\_mem(int target\_task, void *addr, int size, int perms)} creates a SMO of size \textsf{size} words\footnote{The actual unit in which size is expressed is defined by the implementation.} at offset \textsf{addr} of the current task's address space, that can be accessed by the task\footnote{What is meant here is that it can be accessed by any thread of the corresponding task.} \textsf{target\_task}. The parameter \textsf{perms} indicates if access is granted for reading, writing, or both. The function returns an id number that identifies the SMO just created, or -1 in case of failure. SMOs can be destroyed using the system call \textsf{int claim\_mem(int smo\_id)} and the target task of an SMO can pass it over to another task using the system call \textsf{int pass\_mem(int smo\_id, int target\_task)}, which changes the target task to the supplied parameter.

The system call \textsf{int read\_mem(int smo\_id, int off, int size, void *dest)} copies the \textsf{size} words at offset \textsf{off} of the SMO identified by \textsf{smo\_id} to the address \textsf{dest}. Conversely, the system call \textsf{int write\_mem(int smo\_id, int off, int size, void *src)} copies \textsf{size} words from address \textsf{src} from the current task's address space to offset \textsf{off} of the SMO identified by \textsf{smo\_id}. Of course, in both cases the current task must be the target task of the SMOs, and have the right permission.

All the memory-sharing system calls excepting \textsf{share\_mem} return 0 in case of success and -1 otherwise.

\textbf{kernel internals:} Memory sharing functions are the only functions that need to access the address space of a task distinct from the currently executing one. This must be resolved by each platform implementation, providing functions \textsf{arch\_cpy\_from\_task} and \textsf{arch\_cpy\_to\_task} that perform inter-task address translation. See section \ref{sec:lowlevelinterface} for relevant details.

\section{Dynamic Memory} \label{sec:dynamicmemory}

From version 1.5+, Sartoris supports enabling of dynamic memory management at compile time. When enabled, memory for the microkernel structures will be partially allocated\footnote{Initially, only a predefined ammount of space will be preallocated for each type of structure.}.\\
When a system call is issued to the microkernel, requesting the creation of a structure on micorkernel memory\footnote{i.e. Sending a message, creating an SMO, creating a Task/Thread or opening a port.} the microkernel will rise a Page Fault interrupt. The OS, will be able to tell if the interrupt was rised because of a sartoris memory need, by invoking \textsf{get\_page\_fault} syscall, and testing for the value \textsf{0xFFFFFFFF} on task\_id member of the structure sent as a parameter. When servicing a sartoris Dynamic Memory interrupt, the OS on top of Sartoris, *must* issue a \textsf{grant\_page\_mk} syscall, passing the physical address of the page granted to Sartoris. If the physical address is NULL (0), Sartoris will consider no page is available for him, and the system call which generated the need for dynamic memory will fail.\\ 
Whenever Sartoris considers it will no longer require an allocated page, it will also rise a Page Fault interrupt, although this time the operating system will be sent a task\_id of 0xFFFFFFFE upon a call to \textsf{get\_page\_fault}. The physical address of the page being freed by the microkernel, will be sent on the member \textsf{linear} of the structure.\\
While servicing a Dynamic Memory page fault (i.e. with task\_id 0xFFFFFFFF or 0xFFFFFFFE) the Operating System, is free to continue its normal operation, however, when the page fault has task\_id on 0xFFFFFFFF, the OS wont be allowed to run the thread which originated the need for Dynamic Memory allocation, and every call to a syscall which requires Dynamic Memory will fail.

\section{Low-level interface} \label{sec:lowlevelinterface}

The Sartoris microkernel is divided in an architecture neutral section, which is written in the C programming language, and handles the kernel data structures, and an architecture specific section, which handles the processor data structures and its low level management. The interface that defines the low-level functions is located in \textsf{include/sartoris/cpu-arch.h}

\begin{sf} \noindent /* This are the arch-dependent functions needed to support the kernel */ \\
\\
\#ifndef CPUARCH \\
\#define CPUARCH \\
\\
\#include $<$sartoris/kernel.h$>$ \\
\\
void arch\_init\_cpu(void); \\
\\
int arch\_create\_task(int task\_num, struct task* tsk); \\
int arch\_destroy\_task(int task\_num); \\
\\
int arch\_create\_thread(int id, struct thread* thr); \\
int arch\_destroy\_thread(int id, struct thread* thr); \\
int arch\_run\_thread(int id); \\
\\
int arch\_page\_in(int task, void *linear, void *physical, int level, int attrib); \\
int arch\_page\_out(int task, void *linear, int level); \\
int arch\_flush\_tlb(void); \\
\\
void arch\_mem\_cpy\_words(int *src, int *dst, int len); \\
void arch\_mem\_cpy\_bytes(char *src, char *dst, int len); \\
\\
int arch\_cpy\_to\_task(int task, char* src, char* dst, int len); \\
int arch\_cpy\_from\_task(int task, char* src, char* dst, int len); \\
\\
void arch\_dump\_cpu(void); \\
\\
\#ifndef HAVE\_INL\_CLI \\
int arch\_cli(void); \\
\#endif \\
\\
\#ifndef HAVE\_INL\_STI \\
void arch\_sti(int x); \\
\#endif \\
\\
\#ifndef HAVE\_INL\_GET\_PAGE\_FAULT \\
void *arch\_get\_page\_fault(void); \\
\#endif \\
\\
\#ifndef HAVE\_INL\_ISSUE\_PAGE\_FAULT \\
void arch\_issue\_page\_fault(void); \\
\#endif \\
\\
\#ifndef MAKE\_KRN\_PTR \\
\# define MAKE\_KRN\_PTR(x) ((void*)x) \\
\#endif \\
\\
\#ifndef MAKE\_KRN\_SHARED\_PTR \\
\# define MAKE\_KRN\_SHARED\_PTR(t, x) ((void*)x) \\
\#endif \\
\\
int arch\_cli(void); \\
void arch\_sti(int); \\
\\
\#endif \\
\end{sf}
\\
The architecture specific functions are called from the proper system calls. While they may access the rest of the kernel's data, they should define their own architecture specific data structures and reserve the necessary memory regions to hold them. 

\chapter{The x86 implementation}

\section{System organization overview}
Initializing the processor and loading the microkernel and the init-process to main memory is the very fist task that the IA32 specific section of Sartoris must overcome. Once the bootstrapping has concluded, the kernel initialization function must create the system tables and execute the init task, which will start the operating system. 

The main purpose of the architecture specific functions in Sartoris is the management of tasks, threads, paging and locking. In the IA32 architecture, the creation and destruction of tasks updating the descriptors in the Global Descriptor Table and one Local Descriptor Table, so that the user segments have the correct privilege levels and point to the task's memory areas. To perform the multiplexing of the CPU into several threads, the IA32 architecture defines a data structure which contains all the information required to create, suspend and resume a thread, the Task State Segment.

The IA32 kernel code is located in \textsf{arch/i386/kernel/}.

\section{Bootstrapping}

In the PC architecture, bootstrapping begins after the BIOS loads the first 512-byte sector of the boot drive to offset 0x7c00, and executes it in real mode. The boot sector assembly source is in \textsf{arch/i386/boot/boot.s}. It uses BIOS function 0x13 to load the raw area immediately following the boot sector in the boot media to memory, extracting the kernel image and the init task image. Then it jumps to the kernel initialization routines. The boot media and the kernel size are hardcoded in the boot sector for now, so they have to be manually set.

In order to run the kernel, the boot sector must also enable the 20'th address line in the bus, which is done through the keyboard controller and change the processor executing mode to protected mode. Temporary IDT and GDT tables are set up before the switch to protected mode.

\section{Locking}

The ability to enable and disable interrupts is used to implement critical sections that protect the integrity of microkernel data structures. The locking is as fine-grained as possible, without over-complicating the implementation. Some operations, like for example page-table mangling, are completely atomic, since implementing finer locking would require contemplating a too complex scenario. As was explained in \ref{sec:memorymanagement}, page faults are the only traps that are allowed to occur during critical sections. Hence the special measures taken to access user data from system calls.

\section{IA32 system tables}

\subsection{Global Descriptor Table}  \label{subsec:GDT}

The GDT contains the descriptors that are shared among all the tasks in the system. Some descriptors, in particular the LDT descriptors used for tasking and the TSS descriptors used for threading, must reside in the GDT. Some other descriptors that are shared among all the tasks are also in the GDT. The variables \textsf{MAX\_SCA}, \textsf{MAX\_TSK} and \textsf{MAX\_THR} are used to statically reserve entries in the GDT for the maximum possible amount of system calls, tasks and threads. The descriptor layout in the GDT is: \\
\\

\begin{tabular}{|l|l|l|}
\hline
\textbf{descriptor group} & \textbf{how many?} & \textbf{details} \\
\hline
system descriptors & 4 & dummy, kernel code, \\
 & & kernel data, high memory area \\
\hline
syscalls & \textsf{MAX\_SCA} & call gates for the system calls \\
\hline
LDT descriptors & \textsf{MAX\_TSK} & descriptors for task's \\
 & & Local Descriptor Tables \\
\hline
TSS descriptors & \textsf{MAX\_THR} & descriptors for thread's \\
 & & Task State Segments \\
\hline 
\end{tabular}
\\
\\

The very first descriptor of the GDT is a null descriptor, required by the processor architecture\footnote{Loading a zero offset into an unused segment selector register is licit if the corresponding descriptor is null; a protection fault is only generated if a memory access through the null descriptor is attempted.}. The kernel sees the memory as a flat address space. The second descriptor is the kernel code descriptor, which defines a 32 bits execute-read segment with base zero and limit set to 16 megabytes (this is all the maximum amount of memory currently supported), and Descriptor Privilege Level set to zero (most privileged). The third descriptor is the kernel data descriptor, like the second one but with data-read-write type. The fourth descriptor is has a Descriptor Privilege Level of two, and is a data-read-write type descriptor which gives the service level tasks access to the high memory area\footnote{region between the physical addresses 0xa0000 and 0x100000.}, since numerous input output devices are configured to use buffers in this area (ie the standard VGA adapter). The next \textsf{MAX\_SCA} entries are reserved for the system calls' call gates. A call gate allows the microkernel to offer it's services in a controlled way. Each gate has a privilege level (some calls may be accessed from service tasks only), an entry point into the kernel code, and a parameter count. When a thread performs a far call to one of these gates, control is transfered to the kernel and the right amount of parameters are copied to the kernel privilege zero stack. The following descriptors are used to hold the LDTs and the TSS, which will be discussed later in this section. 

\subsection{Interrupt Descriptor Table}

The Interrupt Descriptor Table contains the descriptors that define the processor's reaction to exceptions and external or software generated interrupt. The first 32 entries are reserved for the processor's exceptions, while the rest may be used to handle external interrupts or operating system services invoked through an \textsf{int} instruction. The action taken to add an exception or interrupt handler depends on the type of the thread being created. If it is an \textsf{IRQ\_HDL} thread, a task gate is located in the given offset of the IDT. When this interrupt handler is executed, a task switch is automatically initiated by the processor and the back link field of the handler's task points to the interrupted task's TSS, which is marked busy. The handler must return to the interrupted procedure with an \textsf{iret} instruction, which will initiate a task switch to the interrupted thread. If the thread being created is an \textsf{IRQ\_DRV} thread, the number of the thread is stored and it is used to execute a \textsf{run\_thread} system call each time this interrupt is to be serviced. There is no nesting of tasks.

\subsection{Local Descriptor Tables}

Each LDT must be contained in a special system segment in the GDT. Every task has it's own linear address defined by two descriptors in it's Local Descriptor Table: an execute-read type descriptor for it's code and a read-write descriptor for it's data and stacks.

\subsection{Page Tables}

To define an address space in the IA32 architecture a 4 Kb page directory is needed. This page directory indicates the location in physical memory of the page table corresponding to each chunk of linear space addresses. Then each 4 Kb page table is divided into 1024 4-byte entries that indicate the location in physical memory of a particular page, plus attributes (read, write, cache behavior, etc.). The microkernel has no intermediate structures for holding page mappings, it uses the page tables directly.


\section{IA32 function implementation details}

This section describes the behavior of the IA32 implementation of the architecture dependent functions.

\textsf{arch\_init\_cpu}: 
\begin{enumerate}
\item[]\textbf{PIC reprogramming.} The init functions reprograms the programmable interrupt controllers so that the interrupts from the master controller go to the offsets 32-39 and interrupts from the slave controller go to offsets 40-47 of the IDT. The slave PIC is cascaded through the second interrupt request line of the master. All the interrupts are disabled though the PICs interrupt masks.
\item[]\textbf{GDT set up.} The dummy, kernel code, kernel data and high memory area descriptors of the GDT are created. All the other descriptors are invalidated. The Global Descriptor Table is loaded using the \textsf{lgdt} instruction, which using a virtual descriptor composed by a linear base and a limit located in main memory loads the GDTR register.
\item[]\textbf{syscall hooking.} All the task gates for the system calls are created in the corresponding GDT positions. This is done through the \textsf{hook\_syscall} function, with the correct entry point, privilege level and parameter count for each call, as described in subsection \ref{subsec:GDT}.
\item[]\textbf{IDT set up.} The fist 32 entries of the IDT are filled with interrupt gates\footnote{An interrupt gate is very similar to a call gate, but the processor handles the interrupt enable flag differently.} that point to routines that will dump the cpu registers and information about the currently running task and thread and halt the machine. These handlers should be replaced by the operating system exception handling threads, but for operating system development and to show some diagnostic in case the operating system dies very early in the boot process these default handlers are useful. The rest of the IDT is full with invalid descriptors. Finally, the IDT is loaded in a way analogous to the GDT, using the \textsf{lidt} instruction.
\item[]\textbf{Init service execution} Now the cpu is ready to run the microkernel. Using the \textsf{create\_task} and \textsf{create\_thread} system calls, the operating system init service is created in the exact address to which it was fetched earlier by the bootstrapping code (currently, at the three megabyte mark), and executes using the \textsf{reun\_thread} system call. This is the last action the microkernel will take on it's own initiative.
\end{enumerate}

\textsf{arch\_create\_task}: 
\begin{enumerate}
\item[]\textbf{LDT set up.} An execute-read segment and a read-write segment are created in the task's local descriptor table first and second descriptors, with the privilege level corresponding to the task being created and base and limit according to the corresponding syscall parameters.
\item[]\textbf{create LDT descriptor.} The GDT descriptor for this LDT is created with the correct privilege level.
\end{enumerate}

\textsf{arch\_destroy\_task}: 
\begin{enumerate}
\item[]\textbf{invalidate LDT descriptor.} The task's LDT descriptor is invalidated, preventing any future access to or execution from the task's address space.
\end{enumerate}

\textsf{arch\_create\_thread}: 
\begin{enumerate}
\item[]\textbf{TSS set up.} The Task State Segment holds the contents of all the general purpose registers, the base and stack registers for all the privilege levels, the segment selector registers, the eflags register, the LDT selector register, the instruction pointer register, and a few more that are not used under Sartoris version 0.5. In a new thread's TSS, all the general purpose registers are set to zero. The base and stack pointer for the thread's privilege level are set to the stack value supplied by the call, while the privilege zero base and stack pointer are set to the kernel assigned stack. The unused base and stack registers are set to zero. The cs register is loaded with a selector for the code segment in the task's LDT with the correct Requested Privilege Level, while cs, ds and ss are loaded with the second descriptor in the LDT, the data segment. The ss0 register is loaded with the kernel data segment. The fs and gs registers are loaded with null descriptors, but in service task's threads fs is loaded with a selector for the high memory area descriptor located in the fourth entry of the GDT. The eflags register is loaded with IO Privilege set to 2 (only service tasks can access the IO space), and interrupts disabled iff this is an interrupt handling thread. The LDT selector register is loaded with the task's LDT selector. Finally, the instruction pointer register is loaded with the entry point supplied for the newly created thread.
\item[]\textbf{create TSS descriptor.} Once the TSS is in place, a descriptor in the GDT must be created through which the thread may be started and resumed.
\item[]\textbf{update IDT.} If the thread is of type \textsf{IRQ\_HDL}, the IDT position for the requested interrupt line or exception must be updated, with a task gate that points to the thread's TSS. If the thread is of type \textsf{IRQ\_DRV}, an interrupt gate that points to a special section of the kernel is created, and the number for the thread is saved in an array. Later on, when this interrupt is handled, this special section of the kernel will fetch the thread number and initiate a task switch. 
\item[]\textbf{update interrupt mask.} The interrupt request line must be enabled in the corresponding PIC if this is an external interrupt.
\end{enumerate}

\textsf{arch\_run\_thread}: 
\begin{enumerate}
\item[]\textbf{do task switch.} A task switch to the target thread is initiated by performing a far jump to offset zero of the thread's TSS descriptor in the IDT. No nesting of tasks is produced.
\end{enumerate}

\textsf{arch\_cli}:
\begin{enumerate}
\item[]\textbf{disable interrupts.} The interrupt enable bit of the eflags register is saved and then cleared. The function returns the original value.
\end{enumerate}

\textsf{arch\_sti}:
\begin{enumerate}
\item[]\textbf{enable interrupts.} The previous value of the interrupt enable bit is examined and interrupts are re-enabled only if they weren't disabled before the call to the previous \textsf{arch\_cli}.
\end{enumerate}

\chapter{Final thoughts}

We consider that the microkernel concept provides a natural and adequate layer of abstraction between the management of the central processor, the memory management unit and the interrupt controller and the rest of the operating system. Sartoris, being  a very thin microkernel (even the scheduling is performed outside the kernel), imposes a few performance constraints on the operating system; however, we don't believe this restrictions would hinder the overall performance of the system for all but a few very demanding scenarios. The benefits of a microkernel architecture seem to outweight the small performance hit.

On the implementation front, some features of the IA32 architecture, like processor hardware support for threading using Task State Segments, interrupt handling threads through task gates in the IDT, thread-nesting support through TSS nesting, and call gates to provide controlled access to operating system services, really simplified the implementation of the microkernel. The suspension and re-activation of threads is almost reduced to the execution single machine instruction.

 Asynchronous message passing, the main IPC mechanism of Sartoris, is however not really ideal for the implementation of operating system services. It leaves the burden of synchronization to the server implementator, who is in a different mindset. The original argument for asynchronous message passing was that it would simplify the implementation of a distributed operating system on top of the Sartoris microkernel. However, we believe that an appropiate IDL (interface definition language) is essential to ease the implementation of the aforementioned servers, abstracting the communication one level further. We have devised a simple modification that would ease this problem, and we outline here: each task could have a specific region of memory marked for IPC, one that can be mapped by other tasks. Then IPC calls should just translate pointers to the region of local task memory where the sending task's IPC memory has been mapped.

\end{document}

